Intersymbol interference (ISI) is often a major factor which limits performance of digital communication systems employed to transmit digital data over a time-dispersive channel, such as a telephone line. Over the past few decades, a number of signal processing techniques have been developed for use in receivers for channels subject to ISI. These techniques include the use of linear equalization, a decision feedback equalizer (DFE), and maximum likelihood sequence estimation (MSLE). Both linear and decision feedback equalization are oriented toward simplicity and low complexity, sacrificing performance. On the other hand, an MLSE, such as that described in an article by G. D. Forney, entitled: "Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference," IEEE Transactions on Information Theory, Vol. IT-18, No. 3, May 1972, pp. 363-378, and a maximum a priori (MAP) symbol-by-symbol estimator, as described in an article by K. Abend et al "Statistical Detection for Communication Channels with Intersymbol Interference," Proceedings of the IEEE, Vol. 58, No. 5, May 1970, pp. 779-785, and in an article by J. F. Hayes et al, entitled: "Optimal Sequence Detection and Optimal Symbol-by-Symbol Detection: Similar Algorithms," IEEE Transactions on Information Theory, Vol. IT-18, No. 3, May, 1972, pp. 363-378, seek optimum or near optimum performance, but do so at a cost of substantially increased computational and data storage requirements.
More recently, symbol detection schemes have been developed that approach the performance of these optimal techniques, but at a much lower complexity. These techniques include the reduced state sequence estimator (RSSE), as described in an article by A. Duel-Hallen et al, entitled: "Delayed Decision-Feedback Sequence Estimation," IEEE Transactions on Communications," Vol. 37, May 1989, pp. 428-436, and in an article by M. V. Eyuboglu et al, entitled: "Reduced-State Sequence Estimation with Set Partitioning and Decision Feedback," IEEE Transactions on Communications," Vol. 36, January 1988, pp. 13-20, and the fixed delay tree search (FDTS) mechanism, as described in an article by A. P. Clark et al, entitled: "Developments of the Conventional Nonlinear Equalizer," IEE Proceedings, Vol. 129, Pt. F, No. 2, April 1982, pp. 85-94, articles by J. Moon et al, entitled: "Efficient Sequence Detection for Intersymbol Interference Channels with Run-Length Constraints," IEEE Transactions on Communications, Vol. 42, No. 9, September, 1994, pp. 2654-2660, and "Performance Comparison of Detection Methods in Magnetic Recording," IEEE Transactions on Magnetics, Vol. 26, No. 6, November 1990, pp. 3155-3172, an article by J. G. Proakis et al, entitled: "A Decision-Feedback Tree-Search Algorithm for Digital Communication through Channels with Intersymbol Interference," 1986 ICC Conference Proceedings, pp. 657-661, and an article by D. Williamson et al, entitled: "Block Decision Feedback Equalization," IEEE Transactions on communications, Vol. 40, No. 2, February 1992, pp. 255-264.
The RSSE is a simplification of the MLSE, which reduces complexity by limiting the dimensionality of the trellis. The FDTS scheme is a simplification of the MAP symbol-by-symbol detector, using decision feedback to limit complexity. (In the present description, it is to be understood that the term FDTS applies to general techniques used in a variety of sources under various names, and is not necessarily limited to the specific FDTS/DF proposed in the above-referenced Moon et al article for a magnetic recording channel.) Both of these reduced complexity techniques (RSSE and FDTS) decrease complexity by considering only a portion of channel ISI in the enhanced decision techniques, and using low complexity linear or decision feedback equalization to handle the remaining portion of the ISI.
For the case of pulse amplitude modulation (PAM) communication signals, such as 2B1Q modulation used in high speed data service loop (HDSL) signals, as a non-limiting example, such a dispersive channel may be diagrammatically illustrated in FIG. 1, as a discrete finite impulse response (FIR) additive white Gaussian noise (AWGN) channel model applied to a continuous time linear system with correlated noise by using the whitened matched filter described in the above-referenced Forney article.
In accordance with this discrete model, a sequence of symbols u.sub.i ! chosen from an M-ary alphabet A={-M+1, -M+3, . . . , M-3, M-1} is transmitted. The transport of the input sequence u.sub.i } through the channel h.sub.k, shown at 10 results in the output sequence {y.sub.i }, given by ##EQU1## where {h.sub.k =0, 1, . . . ,N} is the FIR channel response, and {W.sub.i } is a sequence of noise samples, injected or summed at 12, which is white and Gaussian, with a zero mean and a variance .sigma..sup.2.
At the receive end of the channel, the combined noise plus information signal w.sub.i +s.sub.i =y.sub.i is processed by means of a signal processor 14 to produce an output signal sequence u.sub.i-D, representative of what symbols were actually transmitted. As described in the second of the above-referenced Moon et al articles, the FDTS scheme can be viewed as a depth-limited tree-search. It can also be viewed as a limited trellis search, or a multi-dimensional decision space, as described in the Williamson et al article.
FIG. 2 diagrammatically illustrates an M-ary search tree, for the case of 2B1Q signals, as an example, in which the tree has M=4 branches emanating from each node, to represent four possible 2B1Q symbols (-3, -1, +1, +3) at each symbol time. A sequence of input symbols will result in a path through the search tree. Although the search tree may grow exponentially without bound, the FDTS technique limits the size of the tree by making a decision at time i, thus eliminating all paths that do not contain the chosen symbol at that time.
The FDTS mechanism makes a decision at time i by looking ahead D levels in the tree and computing a cumulative error metric for each of the possible paths through the tree, namely M.sup.D+1 paths, each with D+1 branches. The error metric is a function of both the received data, y.sub.i, y.sub.i+1, . . . , y.sub.i+D !, and the symbols associated with the decision path. The decision is the symbol associated with the first branch of the path which has the smallest error metric. Feedback of past decisions {u.sub.m, i-N.ltoreq.m&lt;i} is used to keep the root node of the tree aligned with the decision time i.
The input symbol associated with a branch at time i is denoted by x.sub.i, where x.sub.i .di-elect cons.A. Each path of look-ahead depth j is denoted by the vector of the input symbols associated with each branch in the path: X.sub.i,j =x.sub.i,x.sub.i+1, . . . ,x.sub.i+j !. Each path has associated with it an output symbol, v.sub.i,j (X.sub.i,j), and a last branch error metric, e.sub.i,j (X.sub.i,j). The input to the FDTS is a vector of partially decision-feedback-equalized received signals.
The D+1 components of the input vector Z.sup.i are computed using ##EQU2## for j=0, 1, . . . , D.
Rewriting equation (2) in recursive form as equations (3) and (4) below reveals that the summation represents decision feedback. Namely, ##EQU3## and EQU Z.sub.i+1,j-1 =Z.sub.i,j -u.sub.j h.sub.j,j=1,2, . . . ,D (4)
Equation (3) represents partial decision feedback equalization, where the first D taps of the feedback filter are set to 0, allowing the decision algorithm to make use of the remaining ISI. Equation (4) updates each vector component as a new decision is made and a new sample y.sub.i+D is received.
The decision u.sub.i is formed by searching all M.sup.D+1 tree paths, X.sub.i,D =x.sub.i,x.sub.i+1, . . . ,x.sub.i+D !, and selecting that path U.sub.i+D, which minimizes the cumulative error metric: ##EQU4## is the ideal noise free (partially decision-feedback-equalized) output signal, and e.sub.i,j (X.sub.i,j) is the branch error, for the last branch in the path of look-ahead depth j.
The decision u.sub.i is that symbol associated with the first branch of the path selected: ##EQU5## where the column vector on the right side of equation (7) selects the first component of the path vector.
In the first of the above-referenced articles by J. Moon et al, and the article by Williamson et al, it is shown that, in the absence of past decision errors, this decision metric is asymptotically equivalent to the MAP estimate for the transmitted symbol u.sub.i, given delay D and high-SNR.
Because the conventional FDTS scheme takes into consideration each of the possible M.sup.D+1 paths through the tree, it is both computationally complex and has very substantial data storage requirements.